Table of prime factors
Properties Many properties of a natural number n'' can be seen or directly computed from the prime factorization of ''n. *The multiplicity of a prime factor p'' of ''n is the largest exponent m'' for which ''pm divides n''. The tables show the multiplicity for each prime factor. If no exponent is written then the multiplicity is 1 (since ''p = p''1). The multiplicity of a prime which does not divide ''n may be called 0 or may be considered undefined. *Ω(n''), the big Omega function, is the number of prime factors of ''n counted with multiplicity (so it is the sum of all prime factor multiplicities). *A prime number has Ω(n'') = 1. The first: 2, 3, 5, 7, E, 11, 15, 17, 1E, 25, 27, 31. There are many special types of prime numbers. *A composite number has Ω(''n) > 1. The first: 4, 6, 8, 9, X, 10, 12, 13, 14, 16, 18, 19. All numbers above 1 are either prime or composite. 1 is neither. *A semiprime has Ω(n'') = 2 (so it is composite). The first: 4, 6, 9, X, 12, 13, 19, 1X, 21, 22, 29, 2X. *A ''k-almost prime (for a natural number k'') has Ω(''n) = k'' (so it is composite if ''k > 1). *An even number has the prime factor 2. The first: 2, 4, 6, 8, X, 10, 12, 14, 16, 18, 1X, 20. *An odd number does not have the prime factor 2. The first: 1, 3, 5, 7, 9, E, 11, 13, 15, 17, 19, 1E. All integers are either even or odd. *A square has even multiplicity for all prime factors (it is of the form a''2 for some ''a). The first: 1, 4, 9, 14, 21, 30, 41, 54, 69, 84, X1, 100. *A cube has all multiplicities divisible by 3 (it is of the form a''3 for some ''a). The first: 1, 8, 23, 54, X5, 160, 247, 368, 509, 6E4, 92E, 1000. *A perfect power has a common divisor m'' > 1 for all multiplicities (it is of the form ''am for some a'' > 1 and ''m > 1). The first: 4, 8, 9, 14, 21, 23, 28, 30, 41, 54, 69, 84. 1 is sometimes included. *A powerful number (also called squareful) has multiplicity above 1 for all prime factors. The first: 1, 4, 8, 9, 14, 21, 23, 28, 30, 41, 54, 60. *A prime power has only one prime factor. The first: 2, 3, 4, 5, 7, 8, 9, E, 11, 14, 15, 17. 1 is sometimes included. *An Achilles number is powerful but not a perfect power. The first: 60, 90, 148, 200, 288, 300, 358, 460, 483, 568, 600, 688. *A square-free integer has no prime factor with multiplicity above 1. The first: 1, 2, 3, 5, 6, 7, X, E, 11, 12, 13, 15. A number where some but not all prime factors have multiplicity above 1 is neither square-free nor squareful. *The Liouville function λ(n'') is 1 if Ω(''n) is even, and is -1 if Ω(n'') is odd. *The Möbius function μ(''n) is 0 if n'' is not square-free. Otherwise μ(''n) is 1 if Ω(n'') is even, and is −1 if Ω(''n) is odd. *A sphenic number has Ω(n'') = 3 and is square-free (so it is the product of 3 distinct primes). The first: 26, 36, 56, 5X, 66, 86, 89, 92, 96, XX, E6, 10X. *''a''0(''n) is the sum of primes dividing n'', counted with multiplicity. It is an additive function. *A Ruth-Aaron pair is two consecutive numbers (''x, x''+1) with ''a''0(''x) = a''0(''x+1). The first (by x'' value): 5, 8, 13, 65, X5, 4E6, 670, 92X, X68, 10E2, 1537, 1X68, another definition is the same prime only count once, if so, the first (by ''x value): 5, 20, 41, 65, 88, 109, 269, 350, 4E6, E82, 1277, 13E7. *A primorial x''# is the product of all primes from 2 to ''x. The first: 2, 6, 26, 156, 1406, 15466, 207526, 32E92E6, 62868806, 130682E526, 32X53376556, 9EX23222X9E6. 1# = 1 is sometimes included. *A factorial x''! is the product of all numbers from 1 to ''x. The first: 1, 2, 6, 20, X0, 500, 2E00, 1E400, 156000, 1270000, 11450000, 114500000. 0! = 1 is sometimes included. *A k''-smooth number (for a natural number ''k) has largest prime factor ≤ k'' (so it is also ''j-smooth for any j'' > k). *''m is smoother than n'' if the largest prime factor of ''m is below the largest of n''. *A regular number (number whose reciprocal is terminating dozenal) has no prime factor above 3 (so it is 3-smooth). The first: 1, 2, 3, 4, 6, 8, 9, 10, 14, 16, 20, 23. *A ''k-powersmooth number has all p''m'' ≤ k'' where ''p is a prime factor with multiplicity m''. *A frugal number has more digits than the number of digits in its prime factorization (when written like below tables with multiplicities above 1 as exponents). The first in dozenal: 183, 194, 247, 368, 441, 509, 714, 92E, 1054, 10X1, 1103, 1228. *An equidigital number has the same number of digits as its prime factorization. The first in dozenal: 1, 2, 3, 5, 7, E, 11, 12, 13, 14, 15, 17. *An extravagant number has fewer digits than its prime factorization. The first in dozenal: 4, 6, 8, 9, X, 10, 16, 18, 20, 22, 24, 26. *An '''economical number' has been defined as a frugal number, but also as a number that is either frugal or equidigital. *gcd(m'', ''n) (greatest common divisor of m'' and ''n) is the product of all prime factors which are both in m'' and ''n (with the smallest multiplicity for m'' and ''n). *''m'' and n'' are coprime (also called relatively prime) if gcd(''m, n'') = 1 (meaning they have no common prime factor). *lcm(''m, n'') (least common multiple of ''m and n'') is the product of all prime factors of ''m or n'' (with the largest multiplicity for ''m or n''). *gcd(''m, n'') × lcm(''m, n'') = ''m × n''. Finding the prime factors is often harder than computing gcd and lcm using other algorithms which do not require known prime factorization. *''m is a divisor of n'' (also called ''m divides n'', or ''n is divisible by m'') if all prime factors of ''m have at least the same multiplicity in n''. The divisors of ''n are all products of some or all prime factors of n (including the empty product 1 of no prime factors). The number of divisors can be computed by increasing all multiplicities by 1 and then multiplying them. Divisors and properties related to divisors are shown in table of divisors. Table Category:Pages